package leetcode_ago.top_k;
/**
 * 前k个出现频次最高的元素
 */
import java.util.*;
/**
 * 分析：
 * 1.前k个频次最高的元素，topK问题，用到最小堆（JDK内部默认是最小堆）
 * 2.出现频次最高，是元素值出现次数多的，而非元素值大的，用到键值对（Map集合）
 * 思路：
 * 1.将数组中的元素及出现的次数存到Map集合
 * 2.扫描Map集合，前k个出现频次最高的元素放入最小堆：队中不够k个元素就添加，够了判断是否<堆顶元素，小于不入队，否则堆顶出队当前元素入队
 * 3.最小堆依次出队即可
 * 细节：
 * 1.学会用类解决问题，定义Freq类存储值和出现次数，优先级队列存储的类型就是Freq类
 * 2.此时优先级队列需要传入比较器：因为此时大小关系不是元素值的大小，而是出现频次的大小
 */
public class Num347_TopKFrequent {
    private class Freq implements Comparable<Freq>{
        private int key;
        private int times;

        public Freq(int key, int times) {
            this.key = key;
            this.times = times;
        }
        @Override
        public int compareTo(Freq o) {//最小堆模式
            return this.times-o.times;
        }
    }
    public int[] topKFrequent(int[] nums, int k) {
        int[] ret=new int[k];
        //1.扫描nums数组，每个不重复元素及对应键值对存储到Map集合中
        Map<Integer,Integer> map=new HashMap<>();
        for(int i:nums){
//            map.put(i,map.getOrDefault(i,0)+1);
            if(map.containsKey(i)){
                map.put(i,map.get(i)+1);
            }else{
                map.put(i,1);
            }
        }
        //2.扫描map集合，将前k个出现频次最高的元素放入到优先级队列中
        Queue<Freq> queue=new PriorityQueue<>();
        //Map集合的for-each遍历需要将Map转化为Set
        for(Map.Entry<Integer,Integer> entry: map.entrySet()){
            if(queue.size()<k){
                queue.offer(new Freq(entry.getKey(),entry.getValue()));
            }else{
                Freq freq=queue.peek();//堆顶元素
                if(entry.getValue()< freq.times){
                    continue;
                }else{
                    queue.poll();
                    queue.offer(new Freq(entry.getKey(),entry.getValue()));
                }
            }
        }
        //此时,最小堆内的元素就是需要的元素，依次出队
        for (int i = 0; i < k; i++) {
            ret[i]=queue.poll().key;
        }
        return ret;
    }
}